package 算法.leetcode.labuladong.数组和链表;

/**
 * https://leetcode.cn/problems/count-of-range-sum/
 *
 * @author lchenglong
 * @date 2022/6/15
 */
public class 区间和的个数 {

    static class Solution {

        public static void main(String[] args) {
            int[] nums = new int[]{-2,5,-1};
            int lower = -2,upper = 2;
            Solution solution = new Solution();
            int ans = solution.countRangeSum(nums, lower, upper);
            System.out.println(ans);
        }
        public int countRangeSum(int[] nums, int lower, int upper) {
            // 定义一个前缀数组
            int[] preNums = new int[nums.length+1];
            for (int i=1;i<=nums.length;i++){
                preNums[i] = preNums[i-1]+nums[i-1];
            }
            // 定义双指针
            int left=0,right=nums.length;
            int ans = 0;
            while (left<right){
                int val = preNums[right]-preNums[left];
                if (val>=lower && val<=upper)ans++;
                left++;

            }
            return ans;
        }
    }
}
